There is an ever increasing need to simulate and consider the effect of a wide variety of wave phenomena, such as electromagnetic wave propagation, arising in a variety of environments. Being able to simulate, for example, the dynamics of fluid propagation, heat transfer or electromagnetic radiation is highly advantageous in a number of industries. In particular, electromagnetic field simulation plays an important role in the design and development of electronic products. In this rapidly-changing technology, the time taken in bringing a product to the market place can be critical in maintaining a commercial advantage. In this regard, electromagnetic simulation can provide a highly advantageous tool for design engineers in advancing the development of a device. It may be used, for example, to approximate the surface currents and interior fields arising in complex electronic objects. Electromagnetic simulation is also employed to analyse the electromagnetic radiation emitted by electronic devices, particularly mobile communication devices, in order to assess the health and safety issues for these devices. Furthermore, the study of electromagnetic scattering plays a central role in the design of many complex structures, such as aircrafts, in order to optimise the design and shape of a structure surface. The simulation of convective heat transfer is a useful aid in the analysis and development of ventilation (cooling and/or heating) systems such as those employed in electronic devices. It also provides a tool suitable for use in fire simulation methods which seek to consider the potential fire hazards arising in the electronics industry and other industries.
Generally speaking, the main steps involved in any modelling process are:                1) To define the geometry of a system (i.e. structure or environment) under consideration on a structured grid, taking into account the need to impose boundary conditions on the finite grid as well as the material properties (e.g., for electromagnetic modelling, the magnetic permittivity ε, the magnetic permeability μ, and the electric conductivity ca should be defined);        2) To calculate the numerical solutions for the physical phenomenon under consideration at each node within the grid at a given instant in time; and        3) To provide means for visualising and potentially manipulating the solutions obtained at each time step of the calculation.        
One scheme which finds use in such modelling methods is the FDTD scheme. It was first proposed by Yee in 1966 and is used in a number of computational simulation tools for analysing the behaviour of electromagnetic propagation within a one-, two-, or three-dimensional domain. Broadly speaking, the scheme employs a finite difference and finite time domain approach to discretise the differential form of Maxwell's equations. By this method, derivatives of the electric and magnetic field variables required by Maxwell's equations are approximated by spatial finite differences and the calculation then proceeds in a series of time steps.
In accordance with the FDTD technique, the computational domain or “space” in which the simulation will be performed is represented by a Cartesian grid, discrete in both time and space, comprising a plurality of cells in one, two or three dimensions. FIG. 3 shows a three-dimensional cell, each point of the cell being represented by a set of integers (i, j, k), where i, j and k are grid coordinate numbers in the x-axis, y-axis and z-axis directions respectively. Each of the cells comprises a number of solution points or nodes for the electric and magnetic fields at a given instant in time. In this illustration, the electric field components are defined on the cell faces and the magnetic field components are defined on the cell edges. In accordance with the FDTD principle, the electric field is staggered both spatially and temporally from the magnetic field.
As with any explicit numerical modelling technique, which employs a grid structure for the computational domain, there exists a restriction on the time step Δt with respect to the cell size to ensure stability. Within the FDTD scheme this is given by:
      Δ    ⁢                  ⁢    t    ≤            〈              v        ⁢                                            1                                                〈                                      Δ                    ⁢                                                                                  ⁢                    x                                    〉                                2                                      +                          1                                                〈                                      Δ                    ⁢                                                                                  ⁢                    y                                    〉                                2                                      +                          1                                                〈                                      Δ                    ⁢                                                                                  ⁢                    z                                    〉                                2                                                        〉              -      1      where v is the speed of light in free space.
This stability condition, known as the Courant-Friedrichs-Lewy (CFL) condition, imposes a restriction on the size of the time step Δt in relation to the cell dimensions of the grid.
In many instances, the object or environment to be modelled exhibits so-called inhomogeneities, such as complex or small-scale geometry, or curved boundaries. In order to accurately simulate and consider the effect of these inhomogeneities, the computational domain should preferably allow the numerical solution procedure to capture different levels of detail throughout the system. Analysing electromagnetic fields using a grid which cannot adequately resolve intricate or small-scale structures leads to an inaccurate simulation which, in many applications, can have critical consequences. Obtaining a model of insufficient accuracy is particularly unacceptable in applications where human safety is being investigated, for example analysing the effect of electromagnetic radiation from mobile communication devices on the human body. Furthermore, in complex multi-dimensional situations, for example when trying to simulate and forecast the electromagnetic dynamics for a complex object, such as a laptop computer, it is necessary to be able to resolve and precisely represent the electromagnetic interactions arising within the laptop at component level.
Thus, it is apparent that the grid dimensions (Δx, Δy, Δz) employed in any gridded domain for simulation must be small enough to accurately represent the smallest feature in the model. Naturally, fine geometric features require fine grid cells for precise representation and thus, where a grid is employed throughout the domain in which Δx=Δy=Δz for three dimensions, any spatial refinement needed to resolve small details leads to a global refinement of the computational grid dimensions. Similarly, the simulation of any wave phenomenon varying at a high frequency requires fine grid cells to represent accurately the propagation of the wave with time. If the object under consideration, or a part of it, is a small-scale or complex geometrical structure, such as a wire, it is clear that a fine grid is required accurately to model the field arising in the vicinity of the wire when an electric current is passed through the wire. Similarly, the errors that arise when modelling curved surfaces, due to the way in which they are ‘staircased’ to fit into the Cartesian grid, can be alleviated by employing a higher level of grid refinement.
Thus, to attain accuracy, fine grid cells are essential. An obvious consequence of the need to use fine grid cells in a uniform computational grid is an increase in the number of cells, and thus solution points, in the model. This in turn leads to a higher computing cost in terms of both memory and calculation time. In the example of FDTD schemes, the problem is further compounded by the CFL stability condition which bounds the time step Δt in relation to the grid size so that the finer the grid cell, the smaller the time step Δt, thus further increasing the calculation workload. Software tools developed to analyse three-dimensional, highly intricate, high-frequency models therefore require substantial computing resources in the form of a large memory and high-processing-power central processing units to conduct a simulation that takes a considerable time to run.
Parallel processing, in which the grid is partitioned amongst the processing elements available for a collective computation to attain the solution, offers one means by which the calculation time of a numerical approximation can be reduced. However, this approach is often not cost effective, particularly in complex situations, since any advantage gained in the reduction of the calculation time may be countered by the considerable cost of adding the extra processing elements.
Rather than dividing the entire computational domain into a grid of fine cells, it is known to employ a coarse grid globally over the domain and then to apply one or more fine grids, each fine grid having a plurality of fine-grid cells in regions where they are needed. A domain comprising a coarse grid and having an embedded fine grid is shown in FIGS. 1A and 1B. FIG. 1A shows a two-dimensional coarse grid 20 which is uniformly refined by a fine grid 21 having nine cells for each cell of the coarse grid 20. FIG. 1B shows a three-dimensional coarse grid 22 which is uniformly refined by a fine grid 23 having sixteen cells for each cell of the coarse grid 22. This technique, known as subgridding, can therefore reduce the computational resource requirement by intelligently embedding fine grids locally in regions where they are needed within a coarse-grid model in order to resolve small-scale structures or to improve the modelling of curved boundaries. The savings in both memory and calculation time can be substantial, yet the technique substantially upholds the solution accuracy to that attained by a fine-grid model.
Despite the significant computational advantages that can be achieved by this technique, which circumvents the need to use a very small time step throughout the whole computational domain, subgridding methods are not commonly applied, at least in FDTD, primarily due to numerical instabilities arising at an interface between the coarse and fine grids. The numerical instability arises as a consequence of the discontinuity in the number of solution points at the interface between the coarse grid and the fine grid. In particular, errors are introduced by the temporal and spatial interpolation required to convey information at the interface between the two grids. Non-uniform grids (i.e. individual grids in which the size and shape of cells varies), which are often used in a single grid system, typically suffer from higher errors than uniform grids. Consequently, any previously-used multigrid schemes have employed only grids having uniform, regularly-shaped cells in each grid of the scheme.